package org.jgs1904.apachepoidemo.stack;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

/**
 * @author: 默苍璃
 * @date: 2024-02-27 18:30
 */


import java.util.*;

public class Main {
    public static void main(String[] args) {
        String exp = "x + 2 * (y - 5)";
        SuffixExpression se = compile(exp);
        // Map<String, Integer> env = Map.of("x", 1, "y", 9);
        Map<String, Integer> env = new HashMap<>();
        env.put("x", 1);
        env.put("y", 9);
        int result = se.execute(env);
        System.out.println(exp + " = " + result + " " + (result == 1 + 2 * (9 - 5) ? "✓" : "✗"));
    }

    static SuffixExpression compile(String exp) {
        StringBuilder postfixExp = new StringBuilder();
        Stack<Character> stack = new Stack<>();
        // Map<Character, Integer> priority = Map.of('+', 1, '-', 1, '*', 2, '/', 2);
        Map<String, Integer> priority = new HashMap<>();
        priority.put("+", 1);
        priority.put("-", 1);
        priority.put("*", 2);
        priority.put("/", 2);

        for (char c : exp.toCharArray()) {
            if (Character.isDigit(c) || Character.isAlphabetic(c)) {
                postfixExp.append(c);
            } else if (c == '+' || c == '-' || c == '*' || c == '/') {
                while (!stack.isEmpty() && priority.getOrDefault(stack.peek(), 0) >= priority.getOrDefault(c, 0)) {
                    postfixExp.append(stack.pop());
                }
                stack.push(c);
            } else if (c == '(') {
                stack.push(c);
            } else if (c == ')') {
                while (!stack.isEmpty() && stack.peek() != '(') {
                    postfixExp.append(stack.pop());
                }
                stack.pop(); // 弹出'('
            }
        }

        while (!stack.isEmpty()) {
            postfixExp.append(stack.pop());
        }

        return new SuffixExpression(postfixExp.toString());
    }
}

class SuffixExpression {
    private String postfixExp;

    public SuffixExpression(String postfixExp) {
        this.postfixExp = postfixExp;
    }

    int execute(Map<String, Integer> env) {
        Stack<Integer> stack = new Stack<>();

        for (char c : postfixExp.toCharArray()) {
            if (Character.isDigit(c)) {
                stack.push(Character.getNumericValue(c));
            } else if (Character.isAlphabetic(c)) {
                stack.push(env.get(c));
            } else {
                int operand2 = stack.pop();
                int operand1 = stack.pop();
                int result = performOperation(operand1, operand2, c);
                stack.push(result);
            }
        }

        return stack.pop();
    }

    private int performOperation(int operand1, int operand2, char operator) {
        switch (operator) {
            case '+':
                return operand1 + operand2;
            case '-':
                return operand1 - operand2;
            case '*':
                return operand1 * operand2;
            case '/':
                return operand1 / operand2;
            default:
                return 0;
        }
    }

}
